/*
 * @Author: 生俊甫 1758142861@qq.com
 * @Date: 2024-10-11 20:04:09
 * @LastEditors: 生俊甫 1758142861@qq.com
 * @LastEditTime: 2024-10-15 20:14:31
 * @FilePath: /sjf/2024-project/2024_centos/test_to_c/tree_test/tree.c
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include "tree.h"

void pre_order(BTNode* tree)
{
    if(tree == NULL)
    {
        printf("NULL \n");
        return;
    }
    printf("%d ",tree->_data);
    pre_order(tree->_left);
    pre_order(tree->_right);
}

void in_order(BTNode* tree)
{
    if(tree == NULL)
    {
        printf("NULL \n");
        return;
    }
    in_order(tree->_left);
    printf("%d ",tree->_data);
    in_order(tree->_right);
}

void post_order(BTNode* tree)
{
    if(tree == NULL)
    {
        printf("NULL \n");
        return;
    }
    post_order(tree->_left);
    post_order(tree->_right);
    printf("%d ",tree->_data);
}

//求所有节点数量
int tree_size(BTNode* tree)
{
    return tree == NULL ? 0 : tree_size(tree->_left) + tree_size(tree->_right) + 1;
}
//求所有叶子节点的数量
int tree_leaf_size(BTNode* tree)
{
    if(tree == NULL)
        return 0;
    if(tree->_left == NULL && tree->_right == NULL)
        return 1;
    return tree_leaf_size(tree->_left) + tree_leaf_size(tree->_right);
}
//求第K层节点个数
int tree_k_size(BTNode* tree,int k)
{
    if(tree == NULL) 
        return 0;
    if(k == 1) 
        return 1;
    return tree_k_size(tree->_left, k - 1) + tree_k_size(tree->_right, k - 1);
}
//求深度
int tree_depth(BTNode* tree)
{
    if(tree == NULL)
        return 0;
    int left_depth = tree_depth(tree->_left);
    int right_depth = tree_Depth(tree->_right);
    return  left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}
//寻找值为x的节点
BTNode* tree_find(BTNode* tree,int x)
{
    if(tree == NULL)
        return NULL;
    if(tree->_data == x)
        return tree;
    BTNode* ret1 = tree_find(tree->_left, x);
    if(ret1)
        return ret1;
    BTNode* ret2 = tree_find(tree->_right, x);
    if(ret2)
        return ret2;
    return NULL;
}
//添加新节点
BTNode* buy_node(BNDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    newnode->_data = x;
    newnode->_left = newnode->_right = NULL;
    return newnode;
}
//销毁该树
void tree_destroy(BTNode* tree)
{
    if(tree == NULL)
        return ;
    tree_destroy(tree->_left);
    tree_destroy(tree->_right);
    printf("%p:%d\n",tree,tree->_data);
    free(tree);
}
//层次遍历
void level_order(BTNode* tree)
{
    queue q;
    QueueInit(&q);
    if(tree)
        QueuePush(&q,tree);
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        printf("%d ",front->_data);
        QueuePop(&q);
        //next level
        if(front->_left)
            QueuePush(&q,front->_left);
        if(front->_right)
            QueuePush(&q,front->_right);
    }
    QueueDestroy(&q);
}
/**
 * 2024-10-15复习层次遍历
 * 需要借助队列来实现，基本思路
 * 1.先将根节点如队列
 * 2.循环出队头元素的同时会将该节点的左孩子和右孩子入队
 * 3.依次循环1和2实现层次遍历
 */
void levelorder(BTNode* tree)
{
    queue q;
    QueueInit(&q);
    if(tree)
        QueuePush(&q,tree);
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);//获取到队头元素
        QueuePop(&q);//然后删除该队头元素
        if(front->_left)
            QueuePush(&q,front->_left);//将该删除的头元素的左孩子入队列
        if(front->_right)
            QueuePush(&q,front->_right);//将该删除的头元素的右孩子入队列
    }
    QueueDestroy(&q);
}


//判断该树是否为完全二叉树
bool binary_tree_complete(BTNode* tree)
{
    queue q;
    QueueInit(&q);
    if(tree)
        QueuePush(&q,tree);
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if(front)
        {
            QueuePush(&q,front->_left);
            QueuePush(&q,front->_right);
        }
        else
            break;
    }
    //1.如果后面全是空，则是完全二叉树
	//2.如果箜篌还有非空，则不是完全二叉树
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if(front)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}
